import java.util.*;

public class MyBinaryTree {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        public TreeNode(int val){
            this.val = val;
        }
    }
    TreeNode find(TreeNode root ,int val) {
        if(root == null){
            return null;
        }
        if(root.val == val) {
            return root;
        }
        TreeNode leftroot = find(root.left,val);
        if(leftroot != null) {
            return leftroot;
        }
        TreeNode rightroot = find(root.left,val);
        if(rightroot != null) {
            return rightroot;
        }
        return null;
    }

    public void levelOrder(TreeNode root) {
        if(root == null) {
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            System.out.println(cur.val+" ");
            if(cur.left != null) {
                queue.offer(cur.left);
            }
            if(cur.right != null) {
                queue.offer(cur.right);
            }
        }
    }
    public boolean isBalanced(TreeNode root) {
        if(root == null) {
            return true;
        }
        return TreeHight(root)>0;
    }
    public int TreeHight(TreeNode root) {
        if(root == null){
            return 0;
        }
        int lefthight = TreeHight(root.left);
        if(lefthight < 0){
            return -1;
        }
        int righthight = TreeHight(root.right);
        if(righthight < 0){
            return -1;
        }
        if(Math.abs(lefthight-righthight)<=1) {
            return Math.max(lefthight,righthight)+1;
        }else{
            return -1;
        }
    }
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(root == null){
            return false;
        }
        if(isSameTree(root,subRoot)) {
            return true;
        }
        if(isSubtree(root.left,subRoot)){
            return true;
        }
        if(isSubtree(root.right,subRoot)){
            return true;
        }
        return false;
    }
    public boolean isSameTree(TreeNode p, TreeNode q){
        if((p != null && q == null)||(p == null && q != null)) {
            return false;
        }
        if(p == null && q == null){
            return true;
        }
        if(p.val != q.val) {
            return false;
        }
        return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
    }
    public TreeNode invertTree(TreeNode root) {
        if(root == null) {
            return null;
        }
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        if(root == null) {
            return ret;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> tmp = new ArrayList<>();
            while(size != 0) {
                TreeNode cur = queue.poll();
                tmp.add(cur.val);
                if(cur.left != null) {
                    queue.offer(cur.left);
                }
                if(cur.right != null) {
                    queue.offer(cur.right);
                }
                size--;
            }
            ret.add(tmp);
        }
        return ret;
    }
}
